#include <iostream>

using std::cout;

struct ListNode
{
    int val;
    ListNode *next;
    ListNode() {}
    ListNode(int val, ListNode *next) : val(val), next(next) {}
};



class Solution
{
public:
    #if 0
    ListNode *reverseList(ListNode *head)
    {
        if (head == nullptr || head->next == nullptr)
            return head;
        ListNode *pre = nullptr;
        ListNode *cur = head;

        while (cur != nullptr)
        {
            ListNode *tmp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
    #endif
    ListNode* reverseNode(ListNode* pre,ListNode* cur)
    {
        if(cur == nullptr) return pre;
        // 交换
        ListNode* tmp = cur->next;
        cur->next = pre;
        // pre = cur;
        // cur = tmp;
        return reverseNode(cur,tmp);
    }
    ListNode *reverseList(ListNode *head)
    {
        if (head == nullptr || head->next == nullptr)
            return head;
        return reverseNode(nullptr,head);
    }
    
};

int main(int argc, char const *argv[])
{
    ListNode *head = new ListNode();
    head->val = 1;
    head->next = nullptr;
    ListNode *cur = head;
    for (int i = 1; i < 5; ++i)
    {
        ListNode *newNode = new ListNode();
        newNode->next = nullptr;
        newNode->val = i + 1;
        cur->next = newNode;
        cur = newNode;
    }
    cur = head;
    #if 0
    while (cur)
    {
        cout << cur->val << "\n";
        cur = cur->next;
    }
    #endif

    Solution s;
    cur = s.reverseList(head);
    while (cur)
    {
        cout << cur->val << "\n";
        cur = cur->next;
    }
    getchar();
    return 0;
}
